In analysis of trajectory data of a moving body collected by a sensor such as a global positioning system (GPS), there has been disclosed a technique for generating a route graph from trajectory data.
For example, there has been proposed a method of dividing trajectory data acquired by the GPS into sections in each of which the trajectory data indicate similar movement directions of a moving body, and representing the sections as vectors. In this method, the vectors are clustered based on densities by using similarities and the vectors representing the respective clusters are connected, whereby a graph structure is extracted.
To minimize cost taking dissimilarity between a graph and a trajectory and complexity of the graph into account, there has been proposed a method of associating pieces of trajectory data with the graph based on a Frechet distance or the like and adding unassociated portions to the graph. To generate a route graph, this method starts from an empty graph, and involves performing the above processing once on each piece of the trajectory data.
Japanese Laid-open Patent Publication No. 2015-76069 is an example of the related art.
An example of the related art is described in Jae-Gil Lee, Jiawei Han, Kyu-Young Whang, “Trajectory Clustering: A Partition-and-Group Framework”, SIGMOD '07, June 2007.